package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author qidi
 * @date 2022-01-04 14:36:04
 */
class Q0104_MaximumDepthOfBinaryTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) return 0;

            Deque<TreeNode> q = new ArrayDeque<>();
            Deque<TreeNode> next = new ArrayDeque<>();
            q.add(root);
            int deep = 0;

            while (!q.isEmpty()) {
                TreeNode node = q.pop();
                if (node.left != null) next.add(node.left);
                if (node.right != null) next.add(node.right);

                if (q.isEmpty()) {
                    deep++;
                    q.addAll(next);
                    next.clear();
                }
            }

            return deep;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0104_MaximumDepthOfBinaryTree().new Solution();
    }
}